package com.LeeCode;

/**
 * 向下取整数对和
 */

public class Code1862 {
    public static void main(String[] args) {
        int[] nums = {7, 7, 7, 7, 7, 7, 7};
        System.out.println(new Code1862().sumOfFlooredPairs(nums));
    }

    public int sumOfFlooredPairs(int[] nums) {
        int M = 0;
        for (int num : nums) {
            M = Math.max(M, num);
        }

        int[] freq = new int[M + 1];
        for (int num : nums) {
            freq[num]++;
        }

        // 构建前缀和：prefix[i] = freq[0] + ... + freq[i]
        int[] prefix = new int[M + 1];
        prefix[0] = freq[0];
        for (int i = 1; i <= M; i++) {
            prefix[i] = prefix[i - 1] + freq[i];
        }

        long total = 0;
        final int MOD = 1000000007;

        // 枚举除数 d
        for (int d = 1; d <= M; d++) {
            // 没有出现过
            if (freq[d] == 0) continue;

            // 枚举商 k
            for (int k = 0; k * d <= M; k++) {
                int L = k * d;
                int R = Math.min((k + 1) * d - 1, M);
                if (L > M) break;

                int count = prefix[R] - (L > 0 ? prefix[L - 1] : 0);
                total = (total + (long) k * count * freq[d]) % MOD;
            }
        }

        return (int) total;
    }
}
